//
// Created by Smileyan on 2024/10/30.
// https://www.acwing.com/problem/content/2/

#include <iostream>
#include <vector>

using namespace std;

/**
 * 解决0-1背包问题（每个物品不可重复选择）
 * @param w 背包的最大容量
 * @param weights 物品的重量数组
 * @param values 物品的价值数组
 * @return 返回一个整数，即在容量不超过 w 的情况下，能获得的最大价值
 *
 * 为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮 i - 1 的状态得来的，f[i][j]与f[i - 1][j]是独立的。
 * 而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第 i-1 轮的状态却用的是第i轮的状态。
 */
int knapsack(const int w, const vector<int>& weights, const vector<int>& values) {
    // 物品数量
    const auto n = weights.size();
    // dp[k] 表示当最大容量为 k 时，背包能装物品的最大价值（不装任何物品）
    vector<int> dp(w + 1);
    // 初始化边界，当背包容量为 0 时，背包能装物品的最大价值为 0
    dp[0] = 0;
    // 遍历每个物品，i 表示当前处理的物品索引
    for (int i = 0; i < n; i++) {
        // 从容量 w 开始，倒序遍历容量 j，直到不满足 j >= weights[i] 为止
        // 倒序遍历是01背包的关键，避免重复使用同一个物品
        // 在每轮循环中更新 dp[j] 时，确保 dp[j - weights[i]] 是在更新前的状态，符合01背包的要求
        for (int j = w; j >= weights[i]; j--) {
            // 更新 dp[j] 的值，选择是否放入当前物品。
            // 如果不放入当前物品，dp[j] 保持原值 dp[j]
            // 如果放入当前物品，价值为 dp[j - weights[i]] + values[i]
            // max 函数选择两者中的较大值，更新 dp[j]，确保 dp[j] 存储的是容量为 j 时的最大价值
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    // 返回 dp[w]，即在背包容量为 w 的情况下，可以获得的最大价值
    return dp[w];
}

int main() {
    int n, w;
    cin>>n>>w;
    vector<int> weights(n), values(n);

    for (int i = 0; i < n; i++) {
        cin>>weights[i]>>values[i];
    }
    cout<<knapsack(w, weights, values)<<endl;

    return 0;
}
/*
4 5
1 2
2 4
3 4
4 5

8
*/